package com.mlamp.排序算法;

import java.util.Arrays;

public class 堆排序 {
    public static void main(String[] args) {
        int[] ints = 基础排序.generateArray(30);
        int[] ints1 = heapSort(ints);
        System.out.println(Arrays.toString(ints1));

    }

    public static int[] heapSort(int[] array) {
        int len = array.length;
        if (len < 1) return array;
        buildMaxHeap(array);
        while (len > 0) {
            int temp = array[0];
            array[0] = array[len - 1];
            array[len - 1] = temp;
            len--;
            ajustHeap(array, 0);
        }
        return array;
    }

    public static void buildMaxHeap(int[] array) {
        for (int i = (array.length / 2 - 1); i >= 0; i--) {
            ajustHeap(array, i);
        }

    }

    public static void ajustHeap(int[] array, int i) {
        int maxIndex = i;
        if (i * 2 < array.length && array[i * 2] > array[maxIndex]) {
            maxIndex = i * 2 + 1;
        }

        if (i * 2 + 1 < array.length && array[i * 2 + 1] > array[maxIndex]) {
            maxIndex = (i + 1) * 2;
        }

        if (maxIndex != i) {
            int temp = array[maxIndex];
            array[maxIndex] = array[i];
            array[i] = temp;
            ajustHeap(array, maxIndex);
        }
    }
}
